/**
 * @version Create on 2012-10-31
 * @author Yinzi Chen
 */

public class LargestRectangleInHistgram {

	public int largestRectangleArea(int[] height) {
		int n = height.length;
		if (n == 0)
			return 0;
		int q[] = new int[n + 1];
		q[0] = -1;
		int top = 0;
		int area = 0;
		int l[] = new int[n];
		int r[] = new int[n];
		for (int i = 0; i < n; ++i) {
			while (q[top] != -1 && height[i] <= height[q[top]])
				top--;
			l[i] = height[i] * (i - q[top]);
			q[++top] = i;
		}
		q[0] = n;
		top = 0;
		for (int i = n - 1; i >= 0; --i) {
			while (q[top] != n && height[i] <= height[q[top]])
				top--;
			r[i] = height[i] * (q[top] - i);
			q[++top] = i;
		}
		for (int i = 0; i < n; ++i)
			area = Math.max(area, l[i] + r[i] - height[i]);
		return area;
	}

	public static void main(String[] args) {
		LargestRectangleInHistgram a = new LargestRectangleInHistgram();
		System.out.println(a
				.largestRectangleArea(new int[] { 4, 3, 4, 4, 4, 1 }));
	}

}
